package 剑指offer;

import leetcode.editor.cn.MergeListNode;
import 抽象数据类型.ListNode;

/**
 * @description:
 * @author: ywk
 * @date: 2020-10-25
 */
public class 链表中的节点每k个一组翻转 {
    /**
     * 将给出的链表中的节点每\ k k 个一组翻转，返回翻转后的链表
     * 如果链表中的节点数不是\ k k 的倍数，将最后剩下的节点保持原样
     * 你不能更改节点中的值，只能更改节点本身。
     * 要求空间复杂度 \ O(1) O(1)
     * 例如：
     * 给定的链表是1\to2\to3\to4\to51→2→3→4→5
     * 对于 \ k = 2 k=2, 你应该返回 2\to 1\to 4\to 3\to 52→1→4→3→5
     * 对于 \ k = 3 k=3, 你应该返回 3\to2 \to1 \to 4\to 53→2→1→4→5
     *
     * @param args
     */
    public static void main(String[] args) {
        ListNode root = null;
        root = MergeListNode.proList(new int[]{1, 2, 3, 4, 5}, 0, root);
        MergeListNode.prtList(reverseKGroup(root, 3));

//        MergeListNode.prtList(reverseNode(root));

    }

    /**
     * @param head ListNode类
     * @param k    int整型
     * @return ListNode类
     */
    public static ListNode reverseKGroup(ListNode head, int k) {
        // write code here
        if (head == null) {
            return null;
        }
        ListNode curNode = head;
        int index = 1;
        ListNode tempNode = head;
        ListNode root = null;
        ListNode preNode = head;
        boolean isFirst = true;
        ListNode innerTemp = null;
        while (curNode != null) {
            ListNode temp = curNode.next;
            if (index % k == 0) {
                curNode.next = null;
                ListNode listNode = reverseNode(tempNode);
                if (root != null) {
                    while (innerTemp.next != null) {
                        innerTemp = innerTemp.next;
                    }
                    innerTemp.next = listNode;
                }
                if (isFirst) {
                    root = listNode;
                    innerTemp = root;
                    isFirst = false;
                }
                tempNode = temp;
            }

            curNode = temp;
            index++;
        }
        if (innerTemp != null) {
            while (innerTemp.next != null) {
                innerTemp = innerTemp.next;
            }
            innerTemp.next = tempNode;
        }
        if (root == null) {
            return head;
        }
        return root;
    }

    public static ListNode reverseNode(ListNode root) {
        ListNode curNode = root;
        ListNode preNode = null;
        ListNode nextNode;
        while (curNode != null) {
            nextNode = curNode.next;
            curNode.next = preNode;
            preNode = curNode;
            curNode = nextNode;
        }
        return preNode;
    }
}
